#pragma once

#include<cstdio>
#include<iostream>
#include<set>
#include<vector>
#include<Windows.h>
#include"create_graph.h"
#include"graph.h"

using namespace std;

void check_make_compact_graph(int graph_type, int vertices_number, int edges_number)
{
	string graphname = graph_name(graph_type);
	vector<pair<int, int> > edges;
	if (graphname != "RANDOM")
		edges = get_edges_for_graph_by_type(vertices_number, graph_type);
	else
		edges = get_distinct_edges_for_random_graph(vertices_number, edges_number);
	edges_number = edges.size();
	IGraph* graph = make_compact_graph(vertices_number, edges);
	int list_size = 8 * (2 * sizeof(int) + sizeof(vector<vector<int>>) + vertices_number * sizeof(vector<int>) + edges_number * sizeof(int));
	int matrix_size = 8 * (2 * sizeof(int) + sizeof(vector<vector<bool>>) + vertices_number * sizeof(vector<bool>)) + vertices_number * vertices_number;
	if (! ((list_size > matrix_size) == (graph->graph_representation() == "Matrix")))
		throw logic_error(graphname + "GRAPH: make compact graph: wrong representation choice");
	delete graph;
}

void test_make_compact_graph()
{
	int vertices_number = 1000;
	try
	{
		for (int graph_type = 0; graph_type < NUMBER_OF_GRAPH_TYPES; ++graph_type)
		{
			check_make_compact_graph(graph_type, vertices_number, 0);
		}
		vertices_number = 100;
		int number_of_tests = 100;
		for (int test = 0; test < number_of_tests; ++test)
		{
			check_make_compact_graph(-1, vertices_number, vertices_number);
		}
		for (int test = 0; test < number_of_tests; ++test)
		{
			check_make_compact_graph(-1, vertices_number, vertices_number * vertices_number / 2);
		}
		cout<<"Graps are made compact.\n";
	}
	catch (exception& e)
	{
		cout<<e.what()<<"\n";
	}
	return;
}

void test_memory_of_compact_graph()
{
	int vertices_number = 1000;
	cout<<"Number of vertices is "<<vertices_number<<"\n";
	for (int graph_type = 0; graph_type < NUMBER_OF_GRAPH_TYPES; ++graph_type)
	{
		IGraph* graph = make_compact_graph(vertices_number, get_edges_for_graph_by_type(vertices_number, graph_type));
		cout<<graph_name(graph_type)<<" GRAPH is "<<graph->graph_representation()<<", ";
		if (graph->graph_representation() == "Matrix")
		{
			int size = 8 * (2 * sizeof(int) + sizeof(vector<vector<bool>>) + vertices_number * sizeof(vector<bool>)) + vertices_number * vertices_number;
			cout<<"size: "<<size<<" bits.\n";
		}
		if (graph->graph_representation() == "List")
		{
			int edges_number = graph->get_edges_number();
			int size = 8 * (2 * sizeof(int) + sizeof(vector<vector<int>>) + vertices_number * sizeof(vector<int>) + edges_number * sizeof(int));
			cout<<"size: "<<size<<" bits.\n";
		}
		delete graph;
	}
	return;
}

void check_get_incidence_list(const IGraph* graph, const string& graph_representation)
{
	int vertices_number = graph->get_vertices_number();
	for (int vertex1 = 0; vertex1 < vertices_number; ++vertex1)
	{
		vector<int> incidence_list = graph->get_incidence_list(vertex1);
		set<int> incidence_set(incidence_list.begin(), incidence_list.end());
		for (int vertex2 = 0; vertex2 < vertices_number; ++vertex2)
			if ((incidence_set.find(vertex2) != incidence_set.end()) != graph->is_edge(vertex1, vertex2))
				throw logic_error(graph_representation + " graph: get incidence list: FAILED");
	}
}

void test_get_incidence_list()
{
	try
	{
		int vertices_number = 100;
		int number_of_tests = 100;
		for (int test = 0; test < number_of_tests; ++test)
		{
			int edges_number = (rand() % vertices_number) * (rand() % vertices_number);
			vector<pair<int, int> > edges = get_distinct_edges_for_random_graph(vertices_number, edges_number);
			IGraph* matrix_graph = new MatrixGraph(vertices_number, edges);
			check_get_incidence_list(matrix_graph, "Matrix");
			IGraph* list_graph = new ListGraph(vertices_number, edges);
			check_get_incidence_list(list_graph, "List");
			delete matrix_graph;
			delete list_graph;
		}
		cout<<"Existence of edge list is calculated correctly.\n";
	}
	catch (exception& e)
	{
		cout<<e.what()<<"\n";
	}
	return;
}

void check_is_edge(const IGraph* graph, vector<pair<int, int> > edges_list, const string& graph_representation)
{
	int vertices_number = graph->get_vertices_number();
	set<pair<int, int> > edges_set(edges_list.begin(), edges_list.end()); 
	for (int vertex1 = 0; vertex1 < vertices_number; ++vertex1)
		for (int vertex2 = 0; vertex2 < vertices_number; ++vertex2)
		{
			pair<int, int> edge(vertex1, vertex2);
			if (graph->is_edge(vertex1, vertex2) != (edges_set.find(edge) != edges_set.end()))
				throw logic_error(graph_representation + " graph: is edge: FAILED");
		}
}

void test_is_edge()
{
	try
	{
		int vertices_number = 100;
		int number_of_tests = 100;
		for (int test = 0; test < number_of_tests; ++test)
		{
			int edges_number = (rand() % vertices_number) * (rand() % vertices_number);
			vector<pair<int, int> > edges = get_distinct_edges_for_random_graph(vertices_number, edges_number);
			IGraph* matrix_graph = new MatrixGraph(vertices_number, edges);
			check_is_edge(matrix_graph, edges, "Matrix");
			IGraph* list_graph = new ListGraph(vertices_number, edges);
			check_is_edge(list_graph, edges, "List");
			delete matrix_graph;
			delete list_graph;
		}
		cout<<"Existence of edge list is calculated correctly.\n";
	}
	catch (exception& e)
	{
		cout<<e.what()<<"\n";
	}
	return;
}

class bfs_checker
{
	set<int> used_vertices_;
	bool twice_used_;
	bool non_existing_edge_;
public:
	bfs_checker() {}
	void clear(const IGraph* graph)
	{
		used_vertices_.clear();
		twice_used_ = false;
		non_existing_edge_ = false;
	}

	void on_queue(const IGraph* graph, int vertex_from, int vertex_to)
	{
		if (vertex_from >= 0 && ! graph->is_edge(vertex_from, vertex_to))
			non_existing_edge_ = true;
		if (! (used_vertices_.insert(vertex_to)).second)
			twice_used_ = true;
	}
	
	int used_vertices_number()
	{
		return used_vertices_.size();
	}
	bool twice_used()
	{
		return twice_used_;
	}
	bool non_existing_edge()
	{
		return non_existing_edge_;
	}

	~bfs_checker() {}
};

class dfs_checker
{
	set<int> gray_vertices_;
	bool twice_gray_;
	set<int> black_vertices_;
	bool twice_black_;
	bool non_existing_edge_;
public:
	dfs_checker() {}
	void clear(const IGraph* graph)
	{
		gray_vertices_.clear();
		twice_gray_ = false;
		black_vertices_.clear();
		twice_black_ = false;
		non_existing_edge_ = false;
	}

	void on_stack(const IGraph* graph, int vertex_from, int vertex_to)
	{
		if (vertex_from >= 0 && ! graph->is_edge(vertex_from, vertex_to))
			non_existing_edge_ = true;
	}
	void on_gray(const IGraph* graph, int vertex)
	{
		if (! (gray_vertices_.insert(vertex)).second)
			twice_gray_ = true;
	}
	void on_black(const IGraph* graph, int vertex)
	{
		if (! (black_vertices_.insert(vertex)).second)
			twice_black_ = true;
	}

	int gray_vertices_number()
	{
		return gray_vertices_.size();
	}
	bool twice_gray()
	{
		return twice_gray_;
	}
	int black_vertices_number()
	{
		return black_vertices_.size();
	}
	bool twice_black()
	{
		return twice_black_;
	}
	bool non_existing_edge()
	{
		return non_existing_edge_;
	}

	~dfs_checker() {}
};

void check_bfs(const IGraph* graph, const string& graphname)
{
	bfs_checker bfschecker;
	bfs(graph, -1, &bfschecker);
	if (bfschecker.twice_used())
		throw logic_error (graphname + " GRAPH: vertex was used twice used in bfs");
	if (bfschecker.non_existing_edge())
		throw logic_error (graphname + " GRAPH: non-existing edge was used in bfs");
	if (bfschecker.used_vertices_number() != graph->get_vertices_number())
		throw logic_error (graphname + " GRAPH: some vertices were not used in bfs");
}

void check_dfs(IGraph* graph, const string& graphname)
{
	dfs_checker dfschecker;
	dfs(graph, -1, &dfschecker);
	if (dfschecker.twice_gray())
		throw logic_error (graphname + " GRAPH: vertex was used twice gray in dfs");
	if (dfschecker.twice_black())
		throw logic_error (graphname + " GRAPH: vertex was used twice black in dfs");
	if (dfschecker.non_existing_edge())
		throw logic_error (graphname + " GRAPH: non-existing edge was used in dfs");
	if (dfschecker.gray_vertices_number() != graph->get_vertices_number())
		throw logic_error (graphname + " GRAPH: some vertices did not become gray in dfs");
	if (dfschecker.black_vertices_number() != graph->get_vertices_number())
		throw logic_error (graphname + " GRAPH: some vertices did not become black in dfs");
}

void test_bfs_and_dfs()
{
	int vertices_number = 1000;
	try
	{
		int list_graphs = 0, matrix_graphs = 0;
		for (int graph_type = 0; graph_type < NUMBER_OF_GRAPH_TYPES; ++graph_type)
		{
			IGraph* graph = make_compact_graph(vertices_number, get_edges_for_graph_by_type(vertices_number, graph_type));
			if (graph->graph_representation() == "List")
				++list_graphs;
			else
				++matrix_graphs;
			check_bfs(graph, graph_name(graph_type));
			check_dfs(graph, graph_name(graph_type));
			delete graph;
		}
		int vertices_number = 100;
		int number_of_tests = 100;
		for (int test = 0; test < number_of_tests; ++test)
		{
			int edges_number = (rand() % vertices_number) * (rand() % vertices_number);
			IGraph* graph = make_compact_graph(vertices_number, get_distinct_edges_for_random_graph(vertices_number, edges_number));
			if (graph->graph_representation() == "List")
				++list_graphs;
			else
				++matrix_graphs;
			check_bfs(graph, "RANDOM");
			check_dfs(graph, "RANDOM");
			delete graph;
		}
		cout<<"DFS and BFS are correct.\n";
		cout<<"Number of tested list graphs: "<<list_graphs<<", matrix graphs: "<<matrix_graphs<<"\n";
	}
	catch (exception& e)
	{
		cout<<e.what()<<"\n";
	}
	return;
}

int get_time_of_bfs(IGraph* graph)
{
	bfs_checker bfschecker;
	int time = GetTickCount();
	bfs(graph, -1, &bfschecker);
	time = GetTickCount() - time;
	return time;
}

int get_time_of_dfs(IGraph* graph)
{
	dfs_checker bfschecker;
	int time = GetTickCount();
	dfs(graph, -1, &bfschecker);
	time = GetTickCount() - time;
	return time;
}

void test_time_of_bfs_and_dfs()
{
	int vertices_number = 1000;
	int number_of_tests = 100;
	int sum_bfs_time = 0, sum_dfs_time = 0;
	for (int test = 0; test < number_of_tests; ++test)
	{
		IGraph* sparse_graph = make_compact_graph(vertices_number, get_edges_for_tree_graph(vertices_number));
		sum_bfs_time += get_time_of_bfs(sparse_graph);
		sum_dfs_time += get_time_of_dfs(sparse_graph);
		delete sparse_graph;
	}
	cout<<"On sparse graphs on "<<vertices_number<<" vertices, average time of BFS is "<<sum_bfs_time/number_of_tests<<" ms; DFS - "<<sum_dfs_time/number_of_tests<<" ms\n";
	sum_bfs_time = 0;
	sum_dfs_time = 0;
	number_of_tests = 10;
	for (int test = 0; test < number_of_tests; ++test)
	{
		int edges_number = vertices_number * vertices_number / 2;
		IGraph* dense_graph = make_compact_graph(vertices_number, get_distinct_edges_for_random_graph(vertices_number, edges_number));
		sum_bfs_time += get_time_of_bfs(dense_graph);
		sum_dfs_time += get_time_of_dfs(dense_graph);
		delete dense_graph;
	}
	cout<<"On dense graphs on "<<vertices_number<<" vertices, average time of BFS is "<<sum_bfs_time/number_of_tests<<" ms; DFS - "<<sum_dfs_time/number_of_tests<<" ms\n";
	return;
}

void check_top_sort_on_cycle_graph(const IGraph* graph, const string& graphname)
{
	bool no_cycle = (top_sort_vertices(graph)).first;	
	if (no_cycle)
		throw logic_error(graphname + "GRAPH: top sort did not find a cycle in a cycle graph");
}

void test_top_sort_on_cycle_graphs()
{
	int vertices_number = 1000;
	try
	{
		for (int graph_type = 0; graph_type < NUMBER_OF_CYCLE_GRAPH_TYPES; ++graph_type)
		{
			IGraph* graph = make_compact_graph(vertices_number, get_edges_for_graph_by_type(vertices_number, graph_type));
			check_top_sort_on_cycle_graph(graph, graph_name(graph_type));
			delete graph;
		}
		cout<<"Top sort is correct on cycle graphs.\n";
	}
	catch (exception& e)
	{
		cout<<e.what()<<"\n";
	}
}

void check_top_sort_on_acycle_graph(const IGraph* graph, const string& graphname, vector<pair<int, int> > edges)
{
	pair<int, vector<int> > top_sort_result;
	top_sort_result = top_sort_vertices(graph);
	if (! top_sort_result.first)
		throw logic_error(graphname + "GRAPH: top sort found a cycle in an acycle graph");
	vector<int> sorted_vertices = top_sort_result.second;
	vector<int> number_in_top_sort(graph->get_vertices_number());
	for (int i = 0; i < sorted_vertices.size(); ++i)
		number_in_top_sort[sorted_vertices[i]] = i;
	for (int i = 0; i < edges.size(); ++i)
	{
		if (number_in_top_sort[edges[i].first] > number_in_top_sort[edges[i].second])
			throw logic_error(graphname + "GRAPH: wrong result of top sort");
	}
	return;
}

void test_top_sort_on_acycle_graphs()
{
	int vertices_number = 1000;
	try
	{
		int list_graphs = 0, matrix_graphs = 0;
		for (int graph_type = NUMBER_OF_CYCLE_GRAPH_TYPES; graph_type < NUMBER_OF_GRAPH_TYPES; ++graph_type)
		{
			vector<pair<int, int> > edges = get_edges_for_graph_by_type(vertices_number, graph_type);
			IGraph* graph = make_compact_graph(vertices_number, edges);
			if (graph->graph_representation() == "List")
				++list_graphs;
			else
				++matrix_graphs;
			check_top_sort_on_acycle_graph(graph, graph_name(graph_type), edges);
			delete graph;
		}
		vertices_number = 100;
		int number_of_tests = 100;
		for (int test = 0; test < number_of_tests; ++test)
		{
			int edges_number = (rand() % vertices_number) * (rand() % vertices_number) / 2;
			vector<pair<int, int> > edges = get_distinct_edges_for_random_acycle_graph(vertices_number, edges_number);
			IGraph* graph = make_compact_graph(vertices_number, edges);
			if (graph->graph_representation() == "List")
				++list_graphs;
			else
				++matrix_graphs;
			check_top_sort_on_acycle_graph(graph, "RANDOM", edges);
			delete graph;
		}
		cout<<"Top sort is correct on acycle graphs.\n";
		cout<<"Number of tested list graphs: "<<list_graphs<<", matrix graphs: "<<matrix_graphs<<"\n";
	}
	catch (exception& e)
	{
		cout<<e.what()<<"\n";
	}
	return;
}